package com.c2b.algorithm.leetcode.jzoffer;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/">数组中数字出现的次数 II</a>
 *
 * <p>在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。</p>
 * <p>数据范围：数组长度2≤n≤1000，1 <= nums[i]< 2^31</p>
 * <pre>
 *     示例 1：
 *          输入：nums = [3,4,3,3]
 *          输出：4
 *
 *      示例 2：
 *          输入：nums = [9,1,7,9,7,9,7]
 *          输出：1
 * </pre>
 *
 * @author c2b
 * @since 2023/3/8 13:50
 */
public class JzOffer0056SingleNumber_II {
    /**
     * 考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是3的倍数。 因此，统计所有数字的各二进制位中1的出现次数，并对3 求余，结果则为只出现一次的数字。
     */
    public int singleNumber(int[] nums) {
        // 建立一个长度为 32 的数组 counts，通过以上方法可记录所有数字的各二进制位的1的出现次数。
        int[] counts = new int[32];
        for (int num : nums) {
            for (int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0;
        // 用于拓展，任意次数的都可以
        int m = 3;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }

    public int singleNumber2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            Integer integer = map.getOrDefault(i, 0);
            map.put(i, integer + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue().equals(1)) {
                return entry.getKey();
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        JzOffer0056SingleNumber_II jzOffer0056SingleNumber_ii = new JzOffer0056SingleNumber_II();
        System.out.println(jzOffer0056SingleNumber_ii.singleNumber(new int[]{9, 1, 7, 9, 7, 9, 7}));
    }
}
